1. The Field of the Invention
The present invention relates to the field of data compression and more particularly, to the field of lossless compression and decompression of bi-tonal raster data.
2. The Relevant Art
Raster data is generated by graphical systems when converting graphical objects into a low-level bitstream appropriate for display and rendering. The generated bitstream is often bandwidth and processor intensive, especially in light of the push for systems with higher resolutions and faster rendering speeds. Many graphical systems and products such as page printers, phototypesetters, and electrostatic plotters have dedicated hardware with specialized and often costly architectures optimized for processing the large amounts of graphical data at high speeds.
While image quality and raster data processing requirements continue to increase, market demand for image-oriented devices and systems has proven to be particularly price sensitive. Manufacturers of these devices and systems are under constant pressure to deliver higher resolution systems at lower prices. As a result of these pressures, product life cycles have been dramatically shortened.
Shortened product life cycles make it difficult for manufacturers to recoup the tooling and marketing costs associated with the introduction of new products. Cost-effective components are leveraged to their maximum capacity and performance. Existing devices and systems often have little bandwidth or processing capacity available for new features or enhancements. Ideally, additional features and enhancements must fit within the constraints of existing products and thereby increase their product life cycle at no additional materials cost.
Compression and decompression of raster data offers the hope of reducing the bandwidth requirements at a given rendering resolution and increasing the data throughput and rendering resolution attainable over fixed-bandwidth channels. However, compression algorithms are typically complex and require large amounts of memory and processing power. Large dictionaries of reference data or complex mathematical formulas may be used, each of which requires significant computational resources. Compression algorithms often process a relatively large context of data surrounding a data element in order to spot redundancies or patterns within the raster data. Processing large amounts of data increases both the memory requirements and the processing requirements of compression systems.
From the above discussion, it can be seen that it would be beneficial to improve the performance of graphical systems and other data-intensive systems by providing an apparatus and method for compressing and decompressing data using minimal processing resources. Minimizing the complexity of compressing and decompressing data facilitates handling more data with lower cost components. Low complexity compression also facilitates adding additional capability to existing products and systems at little or no additional cost.
Compression is particularly needed when processing continuous tone images. Continuous tone images are often the preferred output of scanning and imaging devices due to their high image quality. Continuous tone images are particularly large and strain the bandwidth capacity of display and rendering systems. Half-toning is a method of reducing bandwidth requirements by converting continuous tones to ON-OFF patterns of pels (the smallest unit of rendering). One simple half-toning technique is to randomly assign ON and OFF pels with a probability that is proportional to the intensity value at each position within the image.
Half-toning is preferably conducted on scales where the pels are small enough to be perceptually smoothed by the eye. Half-toning is particularly appropriate when the rendering mechanism is bi-tonal in nature such as electro-static printers and plotters. Bi-tonal or digital rendering devices may have multiple colors that are rendered but each color is applied digitally (ON or OFF) on the output medium. One drawback, however, is that half-toning often pushes the limits of rendering technology—particularly when the half-toned image contains many transitions between ON and OFF pels, resulting in poor image compression with conventional compression algorithms. Furthermore, half-tones should be compressed losslessly in such systems, since lossy compression can cause reduced image quality or generate undesirable image artifacts.
Referring to FIG. 1a, the quality of a half-tone image may be improved by reducing transitions between ON and OFF pels. One prior art method, referred to as half-tone screening, concentrates ON and OFF pels into spots by varying a (OFF/ON) threshold value 10 along the horizontal and vertical dimensions of a threshold screen 12. Screening originated within the newspaper publishing industry, and the term “screening” refers to an actual physical screen used to sample photographs and print them as a sequence of dots of varying size. The threshold screen 12 is a modem day equivalent of newspaper screens and is essentially a non-linear filter that produces spots whose size is dependent on the average intensity within a tile 14.
Each tile 14 within a continuous image 16, is half-toned using the threshold screen 12. In the depicted example, the continuous image 16 consists of a two-dimensional array of 8-bit intensity values (0 to 255), and the half-toned tile 18 that is shown contains a diamond shaped spot consisting of 13 pels. The size of the tiles has been enlarged for illustration purposes. The tiles 14 are staggered within the continuous image 16 to reduce the visibility of artifacts within the resulting half-tone image. The threshold values 10 influence the probability of certain half-tone patterns within graphical rendering systems.
From the above discussion, it can be seen that it would be beneficial to improve the performance of rendering systems that process half-tone images by taking advantage of the effects of half-tone screening to better compress raster data. It would also be advantageous to integrate half-tone oriented compression techniques with other techniques optimized for text and line-art. Finally, performing these various techniques with a minimum of system resources facilitates the development of graphical rendering systems with high performance capabilities that are relatively inexpensive to manufacture.